import random
class Solution:
    def maxNumber(self, nums1: list[int], nums2: list[int], k: int) -> list[int]:
        m,n=len(nums1),len(nums2)
        # 找到数组中长度为k且字典序最大的集合
        def findKth(k,nums):
            nn=len(nums)
            stack=[]
            for i,num in enumerate(nums):
                # 必须保证栈中元素和剩下元素总长度之和不小于k
                while stack and stack[-1]<num and len(stack)-1+nn-i>=k:
                    stack.pop()
                stack.append(num)
            return stack[:k]
        
        # 根据字典序合并两个数组
        def merge(a,b):
            m_,n_=len(a),len(b)
            res=[]
            i,j=0,0
            # 比较字典序
            while i<m_ and j<n_:
                if a[i:]>b[j:]:
                    res.append(a[i])
                    i+=1
                else:
                    res.append(b[j])
                    j+=1
            if i<m_:
                res.extend(a[i:])
            if j<n_:
                res.extend(b[j:])
            return res
        
        # 遍历两个数组
        ans=[]
        for i in range(m+1):
            if 0<=k-i<=n:        
                ans=max(ans,merge(findKth(i,nums1),findKth(k-i,nums2)))
        return ans

def generate_test_data(num_tests=10, max_len=10, max_val=9):
    test_cases = []
    for _ in range(num_tests):
        # 随机生成两个数组的长度
        len1 = random.randint(1, max_len)
        len2 = random.randint(1, max_len)
        
        # 随机生成两个数组
        nums1 = [random.randint(0, max_val) for _ in range(len1)]
        nums2 = [random.randint(0, max_val) for _ in range(len2)]
        
        # 随机生成k的值，确保k不大于两个数组的总长度
        k = random.randint(1, len1 + len2)
        
        test_cases.append((nums1, nums2, k))
    
    return test_cases

def test_maxNumber():
    solution = Solution()
    test_data = generate_test_data()
    
    for i, (nums1, nums2, k) in enumerate(test_data):
        print(f"Running test case {i+1}:")
        print(f"nums1 = {nums1}")
        print(f"nums2 = {nums2}")
        print(f"k = {k}")
        
        result = solution.maxNumber(nums1, nums2, k)
        print(f"Result = {result}")
        print()

if __name__ == "__main__":
    test_maxNumber()
